package sf;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 遍历二叉树
 */
public class InterBiTree {

    public static <T extends Comparable<T>> List<T> fistIter(Node<T> root) {
        Deque<Node<T>> stack = new ArrayDeque<>();
        stack.addFirst(root);
        List<T> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            final Node<T> first = stack.removeFirst();
            result.add(first.node);
            if (first.right != null) {
                stack.addFirst(first.right);
            }
            if (first.left != null) {
                stack.addFirst(first.left);
            }
        }
        return result;
    }

    public static class Node<T extends Comparable<T>> {

        private T node;
        private Node<T> left;
        private Node<T> right;

        public T getNode() {
            return node;
        }

        public void setNode(T node) {
            this.node = node;
        }

        public Node<T> getLeft() {
            return left;
        }

        public void setLeft(Node<T> left) {
            this.left = left;
        }

        public Node<T> getRight() {
            return right;
        }

        public void setRight(Node<T> right) {
            this.right = right;
        }
    }

}
